#include<bits/stdc++.h>
#define int long long
using namespace std;
int T,n,m,cnt,flg[3010][3010],f[3010],ans;
struct node{
	int u,v,x;
}a[9000010];
bool cmp(node p,node q){
	return p.x<q.x;
}
int find(int x){
	if(x==f[x]) return x;
	return f[x]=find(f[x]);
}
signed main(){
	freopen("up.in","r",stdin);
	freopen("up.out","w",stdout);
	scanf("%lld",&T);
	while(T--){
		ans=0;
		scanf("%lld%lld",&n,&m);
		if(m==0){
			printf("%lld\n",n-1);
			continue;
		}
		for(cnt=1;cnt<=m;cnt++){
			scanf("%lld%lld%lld",&a[cnt].u,&a[cnt].v,&a[cnt].x);
			flg[a[cnt].u][a[cnt].v]=1;
		}
		cnt--;
		for(int i=1;i<=n;i++){
			f[i]=i;
			for(int j=i+1;j<=n;j++)
				if(flg[i][j]==0) a[++cnt]={i,j,j-i};
		}
		for(int i=1;i<=m;i++)
			flg[a[i].u][a[i].v]=0;
		sort(a+1,a+cnt+1,cmp);
		for(int i=1;i<=cnt;i++)
			if(find(a[i].u)!=find(a[i].v)) f[find(a[i].u)]=find(a[i].v),ans+=a[i].x;
		printf("%lld\n",ans);
	}
	return 0;
}
